import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Auther: 我爱双面奶
 * @Date: 2018/7/18 22:53
 * @Description: 中缀(infix)表达式转波兰式(polish notation)(前缀表达式)
 *
 */
public class InfixToPNCalculate {

    public static void main(String[] args) {
        String str = "1+(6/2)-8*2+(20-4)";
        List<String> pnStack = infixToPn(str);
        int result = getResrult(pnStack);
        System.out.println("结果："+result);
    }

    /**
     * 中缀转前缀表达式算法
     *
     * 1、初始化两个栈：运算符栈opStack和存储前缀表达式栈pnStack；
     * 2、【反转】字符串，【从左至右】扫描中缀表达式；
     * 3、遇到操作数时，直接将其压入tempStack中；
     * 4、遇到运算符时，比较其与opStack栈顶运算符的优先级：
     *       4.1、如果opStack为空，或者栈顶运算符为右括号’)’，则直接将此运算符压入opStack中；
     *       4.2、否则，若优先级比栈顶运算符的优先级高或相等，则直接将此运算符压入opStack中；
     *       4.3、否则，将opStack栈顶的运算符弹出并压入到tempStack中，再次转入步骤4，与opStack中新的栈顶运算符相比较；
     * 5、遇到括号时：
     *       5.1、如果是右括号’)’，则直接压入opStack中；
     *       5.2、如果是左括号’(‘，则依次弹出opStack栈顶的运算符并压入tempStack中，知道遇到右括号’)’为止，此时将这一对括号丢弃；
     * 6、重复步骤2~5，直到表达式的最左边；
     * 7、将opStack中剩余的运算符依次弹出并压入tempStack中；
     * 8、依次弹出tempStack中的元素保存到result中，result即为中缀表达式转换所得的前缀表达式。
     * @param strExpression 前缀表达式
     * @return 后缀表达式
     */
    public static List<String> infixToPn(String strExpression){
        StringBuilder stringBuilder = new StringBuilder(strExpression.trim());//将String对象转换为StringBuilder对象，为了转字符串
        System.out.println("中缀表达式："+stringBuilder);
        stringBuilder = stringBuilder.reverse();//反转字符串
        List<String> pnStack = new ArrayList();//前缀表达式栈
        List<String> opStack = new ArrayList();//运算符栈

        String falg = "";
        char[] str = stringBuilder.toString().toCharArray();
        //从左往右扫描
        for(int i=0;i<str.length;i++ ){
            if(isDigit((falg+str[i]).trim())){//判断flag+当前字符是否为数字
                falg = (falg+str[i]).trim();
                if(i==str.length-1){//当当前字符是数字，并且是最后一个字符时直接存入前缀表达式栈
                    //由于之前反转了，现在要反转回来，比如45在之前被反转为了54，需要反转回来
                    pnStack.add(new StringBuilder(falg).reverse().toString());
                }
            }else {//当当前字符不是数字时
                if(falg.trim()!=""&&isDigit((falg).trim())){//将上一次的flag存入前缀表达式栈
                    pnStack.add(new StringBuilder(falg).reverse().toString());
                    falg="";
                }
                if(opStack.size()==0||opStack.get(opStack.size()-1).equals(")")){//对应4.1
                    opStack.add(String.valueOf(str[i]));
                }else if(str[i]==')'){//对应5.1
                    opStack.add(String.valueOf(str[i]));
                }else if(str[i]=='('){//对应5.2
                    while (opStack.size()!=0){
                        if(opStack.get(opStack.size()-1).equals(")")){
                            opStack.remove(opStack.size()-1);
                            break;
                        }
                        pnStack.add(opStack.get(opStack.size()-1));
                        opStack.remove(opStack.size()-1);
                    }
                }else if (str[i]=='*'||str[i]=='/'){//对应4.2
                    opStack.add(String.valueOf(str[i]));
                }else if(opStack.get(opStack.size()-1).equals("*")||opStack.get(opStack.size()-1).equals("/")){//对应4.3
                    pnStack.add(opStack.get(opStack.size()-1));
                    opStack.remove(opStack.size()-1);
                    i--;
                }else {//对应4.2
                    opStack.add(String.valueOf(str[i]));
                }
            }
        }
        //对应7
        while (opStack.size()!=0){
            pnStack.add(opStack.get(opStack.size()-1));
            opStack.remove(opStack.size()-1);
        }
        //反转List对象
        Collections.reverse(pnStack);
        System.out.print("波兰式(前缀表达式)：");
        pnStack.stream().forEach(x-> System.out.print(x+" "));//迭代输出
        System.out.println("");
        return pnStack;
    }

    /**
     * 通过前缀表达式计算结果
     * 1、借助中间结果栈tempStack，【从右至左】扫描表达式
     * 2、遇到操作数时，将操作数入tempStack栈
     * 3、遇到操作符时，从tempStack栈中弹出两个操作数，进行运行，然后将运算结果压入tempStack栈。
     * 4、重复1~3，直到pnStack为空
     * 5、tempStack栈剩下的最后一个元素即所求结果
     * @param pnStack 中间结果栈
     * @return
     */
    public static int getResrult(List<String> pnStack){
        int result = 0;
        List<String> tempResultStack = new ArrayList<>();

        while (pnStack.size()!=0){
            int end = pnStack.size()-1;
            int resultend = tempResultStack.size()-1;
            if(isDigit(pnStack.get(end))){//对应2
                tempResultStack.add(pnStack.get(end));
                pnStack.remove(end);
            }else {//对应3
                if(pnStack.get(end).equals("*")) {
                    result = Integer.parseInt(tempResultStack.get(resultend)) * Integer.parseInt(tempResultStack.get((resultend - 1)));
                }else if (pnStack.get(end).equals("/")){
                    result = Integer.parseInt(tempResultStack.get(resultend)) / Integer.parseInt(tempResultStack.get((resultend - 1)));
                }else if (pnStack.get(end).equals("+")){
                    result = Integer.parseInt(tempResultStack.get(resultend)) + Integer.parseInt(tempResultStack.get((resultend - 1)));
                }else if (pnStack.get(end).equals("-")){
                    result = Integer.parseInt(tempResultStack.get(resultend)) - Integer.parseInt(tempResultStack.get((resultend - 1)));
                }
                pnStack.remove(end);
                tempResultStack.remove(resultend);
                tempResultStack.remove(resultend-1);
                tempResultStack.add(String.valueOf(result));
            }
        }
       // System.out.println(tempResultStack.toString());
        return result;
    }

    /**
     * 判断一个字符串是否为数值
     * @param str 判断的字符串
     * @return 返回一个boolean值
     */
    public static boolean isDigit(String str){
        return str.matches("[0-9]{1,}");
    }

}
